package greedy

// https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/
// 最小的二进制翻转次数
// 算法: 滑动窗口+贪心，贪心的思路: 前面为非0 的必然要先翻转（否则永远不可能翻转成1）
// 但是 需要一个额外的数组来记录 当前位置是否已经被翻转过，以减小时间复杂度
// flipTimes 表示当前节点翻转的次数，isFlip 表示当前节点是否被翻转
// isFlip[i] = flipTimes[i-k+1] ^ flipTimes[i-k+2] ^ ... flipTimes[i-1] ^ 是否需要被翻转
//           = lastFlipTimes ^ flipTimes[i-k] ^ 是否需要被翻转
// ^ flipTimes[i-k] 相当于将窗口向右移动
// flipTimes[i] = isFlip[i]
// 优化后的时间复杂度: O(n)
// 题解: https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/hua-dong-chuang-kou-tan-xin-by-sysusmiel-gjam/
func MinKBitFlips(A []int, K int) int {
	hasFlip := make([]int, len(A))
	totalCost := 0
	lastFlipTime := 0
	for index, value := range A {
		// 首先计算当前节点被翻转过的次数
		if index >= K {
			lastFlipTime = lastFlipTime ^ hasFlip[index-K]
		}
		// 然后判断当前节点是否需要翻转
		if (value == 0 && lastFlipTime == 0) || (value == 1 && lastFlipTime == 1) {
			// 特殊情况: 最后剩下的元素数量已经不及K 个，但是依然要翻转，直接返回不可能
			if len(A)-index < K {
				return -1
			}
			totalCost++
			lastFlipTime ^= 1
			hasFlip[index] = 1
		}
	}
	return totalCost
}
